package easy;

public class MaximumSubarray {
    //枚举法，超时
    public int maxSubArray0(int[] nums) {
        int max = nums[0];
        for(int i=1;i<=nums.length;i++){
            for(int j=0;j<nums.length;j++){
                int tempMax = 0;
                for(int k=0;k<nums.length-i+1;k++){
                    for(int l=k;l<k+i;l++){
                        tempMax+=nums[l];
                    }
                }
                if(tempMax>max){
                    System.out.println(i);
                    System.out.println(j);
                    max = tempMax;
                }
            }
        }
        return max;
    }

    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int [] sums = new int[n];
        sums[0] = nums[0];
        int max = sums[0];
        for(int i=1;i<n;i++){
            sums[i] = nums[i] + ((sums[i-1]>0)?sums[i-1]:0);
            max = Math.max(sums[i],max);
        }
        return max;
    }
}
